在监督学习中，算法根据训练集，试图模仿类似标签 $y$ 的输出。在这个背景下，每一个输入 $x$，其标签都给出了一个毫无争议的正确答案。相反，对于许多连续决策和控制问题，很难给学习算法提供类似明确的监督。例如，假设我们造好令一个四足机器人，想要编程让其走路，那么起初我们对于走路所需要的行动毫无概念，也就无法为算法提供准确的监督。
在强化学习框架中，我们只给学习算法提供强化函数 reward function，提示学习主体是学习得好或不好。对于四足机器人的例子，前进时强化函数给予机器人正向激励，后退或跌倒时给予负向激励。学习算法则需要在跨时间周期中学习如何行动以获得最大激励。
强化学习在直升机自动驾驶、机器人行走、手机网络路由、市场战略选择、工厂管理、高效网页索引方面都有非常成功的应用。在介绍强化学习之前，我们首先将学习马尔可夫决策过程，马尔可夫决策过程为强化学习建立了正式的讨论框架。
本节包括以下内容：
马尔可夫决策过程包含一组元素 $(S, A, \{P_{sa}\}, \gamma, R)$，其中
马尔可夫决策过程如下：从某个状态 $s_0$ 开始，选择某个动作 $a_0 \in A$，由于这个选择，马尔可夫过程的状态位将根据概率分布 $P_{s_0a_0}$ 随机迁移到某个状态 $s_1$。接下来，选择某个动作 $a_1$，由于这个选择，状态位再次根据概率分布 $P_{s_1a_1}$ 迁移到某个状态 $s_1$。继续选择动作 $a_2$，并依次往复。
整个过程中的总体收益，根据下面这个公式计算 $$ R(s_0,a_0) + \gamma R(s_1,a_1) + \gamma^2 R(s_2,a_2) + \cdots $$ 或者，当把强化函数仅写成状态位的函数时，有 $$ R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots $$
在本节后续的推导中，将使用只包含状态的强化函数。但推广到状态-动作的强化函数也十分容易。
强化学习的目标，是在一个长期的时间段内，选择一组动作，使得总体收益的期望最大化： $$ E[R(s_0)+\gamma R(s_1)+\gamma R(s_2)+\cdots] $$ 注意到，第 $t$ 步的收益通过因子 $\gamma^t$ 进行贴现。从而要使期望值最大化，我们希望正向激励出现得越早越好。
任何函数将状态映射到动作的函数 $\pi: S \rightarrow A$ 都被称为策略 Policy。只要处于状态 $s$，我们就采用动作 $a=\pi(s)$，这时称我们在执行 executing策略 $\pi$。针对策略 $\pi$，定义价值函数 value function如下： $$ V^{\pi}(s) = E[R(s_0)+\gamma R(s_1)+\gamma^2 R(s_2)+\cdots|s_0=s,\pi] $$ $V^{\pi}(s)$ 其实就是从状态 $s$ 开始，持续根据策略 $\pi$ 采取相应的动作，所获得贴现回报总和的期望值。
每个一个固定的策略 $\pi$，其价值函数 $V^{\pi}$ 满足贝尔曼方程 Bellman equations $$ V^{\pi}(s) = R(s) + \gamma \sum_{s^{\prime} \in S} P_{s\pi(s)}(s^{\prime})V^{\pi}(s^{\prime}) $$ 这里将 $V^{\pi}(s)$ 分解为两部分：1）中间回报 $R(s)$，也就是只计算初始状态的收益。2）未来贴现回报的期望总和。仔细考察第二项，求和的部分也可以写做 $E_{s^{\prime} \sim P_{s\pi(s)}}[V^{\pi}(s^{\prime})]$。这是从状态 $s^{\prime}$ 开始的贴现回报总和的期望，而 $s^{\prime}$ 根据概率分布 $P_{s\pi(s)}$ 求得，这个概率分布，有时对初始状态 $s$ 施加动作 $\pi(s)$ 之后获得的。也就是说，第二项恰好是马尔可夫过程第一步后的贴现回报总和的期望。
贝尔曼方程可以有效地用于求解 $V^{\pi}$。具体来说，在有限状态的马尔可夫过程中（$|S| \lt \infty$），对每一个状态 $s$ 都可以写出对于的 $V^{\pi}(s)$。于是我们就有令一组共 $|S|$ 个线性方程，包含 $|S|$ 个变量（每个状态的 $V^{\pi}(s)$），从而可以求解。
定义最优价值函数 optimal value function为 $$ V^*(s) = \max_{\pi} V^{\pi}(s) $$ 这个就是使用任何策略所能达到的贴现回报总和的期望最大值。贝尔曼方程也有一个最优价值函数的版本 $$ V^*(s) = R(s) + \max_{a \in A}\gamma \sum_{s^{\prime} \in S} P_{sa}(s^{\prime})V^*(s^{\prime})) $$
另外，定义策略 $\pi^*: S \rightarrow A$ 如下： $$ \pi^*(s) = arg \max_{a \in A} P_{sa}(s^{\prime})V^*(s^{\prime})) $$ $\pi^*(s)$ 给出的动作 $a$ 可以使最优价值函数取得最大值。
事实上，对于每一个状态 $s$ 和所有策略 $\pi$，都有 $$ \pi^*(s) = V^{\pi^*}(s) \geq V^{\pi}(s) $$
$\pi^*$ 对所有状态 $s$ 都是最优策略。因此我们可以不用管马尔可夫过程的初始状态。
接下来将介绍两种求解有限状态（$|S| \lt \infty$）有限动作（$|A| \lt \infty$）马尔可夫决策过程的有效算法。
第一个算法是值迭代 value iteration，其过程如下：
在算法的内部循环中，有两种方法用来进行更新。第一种，可以先计算所有状态 $s$ 的 $V(s)$，然后覆盖所有的旧值。这称为同步 synchronous更新。相应地，异步 asynchronous更新则每次处理一个状态，更新其对应的值。
不论同步更新还是异步更新，$V$ 都会最终收敛到 $V^*$。有了 $V^*$，则根据上节的公式，可以求解最优策略。
第二个算法是策略迭代 policy iteration，其过程如下：
经过有限次迭代，$V$ 会最终收敛到 $V^{*}$，而 $\pi$ 会最终收敛到 $\pi^*$。
值迭代和策略迭代都是求解马尔可夫过程的标准算法，目前对于两种算法哪种更好并无统一的共识。对于较小的马尔可夫过程，策略迭代通常可以再更少的迭代次数中收敛。相反，对于拥有较大状态空间的马尔可夫过程，策略迭代中显示地计算 $V^{\pi}$ 会需要求解非常大的线性空间，从而造成一定困难，这时值迭代是更适合的方法。出于这个原因，在实际使用中，值迭代的情况会更多。
目前，我们讨论马尔可夫过程和算法，都假定状态迁移的概率和奖励已知。但在很多实际的问题中，二者都不是显式给定的，必须通过数据来预测。（通常，$S, A, \gamma$是已知的）
比如说，我们有一组马尔可夫决策过程的数据（数据可能截止于决策过程中止，或者对于无中止条件的决策给定有限多步），则可以根据最大似然估计法，预估状态迁移的概率 $$ P_{sa}(s^{\prime}) = \frac{状态s时采取动作a并得到状态s'的次数}{状态s时采取动作a的次数} $$ 或者，当上述比值为 $0/0$ 时，对应则在状态 $s$ 下数据中从未采取过动作 $a$——这时，可以预计平均分布，即 $P_{sa}(s^{\prime})=1/|S|$。
随着MDP的进行，我们可以积累更多的数据，上面这个比值是可以通过累计计数增量更新的。
按照类似的思路，如果 $R$ 未知，可以预计状态 $s$ 下的奖励 $R(s)$ 为状态 $s$ 获得的平均奖励。
在有了MDP的基本参数后，建立模型后，则可以通过值迭代或者策略迭代来求解。
In [ ]: